package Hot100.leetcode.editor.cn.code.子串;
//Java：最小覆盖子串
public class MinimumWindowSubstring{
    public static void main(String[] args) {
        Solution solution = new MinimumWindowSubstring().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        
        // 使用数组代替HashMap提高性能，ASCII码范围是0-127
        int[] need = new int[128];
        int[] window = new int[128];
        
        // 统计t中每个字符出现的次数
        for (char c : t.toCharArray()) {
            need[c]++;
        }
        
        int left = 0, right = 0;
        int valid = 0; // 窗口中满足need条件的字符个数
        int needCount = 0; // 需要满足的不同字符数量
        
        // 计算需要满足的不同字符数量
        for (int i = 0; i < 128; i++) {
            if (need[i] > 0) {
                needCount++;
            }
        }
        
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        
        while (right < s.length()) {
            // c是将移入窗口的字符
            char c = s.charAt(right);
            // 扩大窗口
            right++;
            
            // 进行窗口内数据的一系列更新
            if (need[c] > 0) {
                window[c]++;
                if (window[c] == need[c]) {
                    valid++;
                }
            }
            
            // 判断左侧窗口是否要收缩
            while (valid == needCount) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                
                // d是将移出窗口的字符
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                
                // 进行窗口内数据的一系列更新
                if (need[d] > 0) {
                    if (window[d] == need[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}